96. 不同的二叉搜索树

题目链接
代码随想录

分析

我们首先还是把 dp[i] 定义为 i 个节点有多少种满足二叉搜索树的种数，然后我们开始思考状态转移公式。
其实我们对于二叉树首先要明白一点，确定一个二叉树，其实第一步就是确定这个二叉树的根节点，n=3 的时候，有 1，2，3 三个节点，我们如何确定这三个节点能构成的二叉搜索树呢？

• 以 1 为根结点，左侧 0 个节点，右侧 2 个节点，两个节点可以构造成多少种二叉搜索树呢？dp[2],也就是说，当我们选择 1 来当根节点的时候，只有 dp[2] 种方式，
• 以 2 为根节点的时候，左侧有 1 个节点，右侧也只有 1 个节点，总共有 dp[1]*dp[1] 种方式，
• 以 3 为根节点的时候，左侧有 2 个节点，右侧有 0 个，总共有 dp[2] 种方式
  所以 dp[3] = dp[2] + dp[1]*dp[1] + dp[2]。
  所以状态转移公式是 dp[i] = dp[i-1] + dp[i-2]*dp[1] + dp[i-3]*dp[2] + ... + dp[1]*dp[i-2] + ... + dp[i-1]；
  初始值就是 dp[1]。i 从 2 开始。

解题

public int numTrees(int n) {
    if(n==1){
        return n;
    }
    int[] dp = new int[n+1];
    dp[1]=1;
    for(int i=2;i<=n;i++){
        int count=0;
        for(int j=1;j<=i;j++){
            int leftNodeCount = j-1;
            int rightNodeCount = i-j;
            // 也可以把dp[0]初始化成1，但是是没有意义的，不要这样做。
            int leftCount = leftNodeCount==0?1:dp[leftNodeCount];
            int rightCount = rightNodeCount==0?1:dp[rightNodeCount];
            count+=leftCount*rightCount;
        }
        dp[i]=count;
    }
    return dp[n];        
}

相关题